package 校赛.真题._2022校赛;

import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec
 * 题目描述
 * 小A是一个游戏天才，他在游戏中几乎不会输，但在这样一款游戏中，他即使打败了所有对手，也无法获得全部的胜利。
 * 这是一个有n关的闯关游戏，每一关结束后有一个目标分数targeti，若结束时所得分数大于等于目标分数，则算胜利一次。
 * 每关游戏有两个等级：简单和困难，通过不同难度的模式，会获得不同的分数，初始默认是n关都是简单的游戏，
 * 但是小A为了能获得更多次的胜利，他可以将不超过m关的难度提升为困难，
 * 这样他可以得到更多的分（因为小A是个游戏天才，所以他一定会过关，获得相应分数），并且他可以自由的决定关卡的挑战顺序。
 * 如何合理地重新排列数组的关卡的挑战顺序（也可以保持不变），并合理使用不超过m次提升难度的次数，
 * 能让你帮小A获得最多次的胜利，请你算小A算算他最多可以获得多少次胜利。

 * 输入格式
 * 第一行包含两个数n和m，n代表有多少个数，m代表难度提升的次数。
 * 第二行包含n个数，第i个数代表第i论的目标分数targeti。
 * 接下来n行，每行分别是一个aj（简单难度的分数），一个bj（困难难度的分数）。

 * 输出格式
 * 一个值，小A最多的获胜次数。

 * 数据范围
 * 1 ≤ m≤ n≤ 15,≤ 100000
 * -100000 ≤ targeti ≤ 100000
 * -100 ≤ aj,bj≤ 100

 * 样例1
 * 输入数据 1
3 1
5 7 9
1 1
2 3
2 5
 * 输出数据 1
 * 2
 * 样例1解释
 * 首先选第三关2 5，难度提升到困难，获得分数5。当前累计分数5大于等于目标分数5，获胜1次，获胜次数为1次。
 * 然后选第二关2 3，难度保持简单，获得分数2。当前累计分数7大于等于目标分数7，获胜2次。
 * 最后选第一关1 1，难度保持简单，获得分数1。当前累计分数8 小于目标分数9 ，未获胜。
 * 总获胜次数为2次，输出2。
 * @since 2023 - 03 - 28 - 10:55
 */
public class E_过五关斩六将 {
}
class Main_E{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        int[] targets = new int[n];
        for(int i = 0; i < n; i++){
            targets[i] = sc.nextInt();
        }
        int[][] choices = new int[n][2];
        for(int i = 0; i < n; i++){
            choices[i][0] = sc.nextInt();
            choices[i][1] = sc.nextInt();
        }
        int res = 0;
        //二进制枚举
        int cnt;
        for(int i = 0; i < (1 << n); i++){
            //1表示提升到困难
            cnt = 0;
            for(int j = 0; j < n; j++){
                if(((i >> j) & 1) == 1) cnt++;
            }
            //合法情况
            if(cnt <= m){
                //大顶堆
                PriorityQueue<Integer> queue = new PriorityQueue<>((e1, e2) -> e2 - e1);
                for(int j = 0; j < n; j++){
                    if(((i >> j) & 1) == 1) {
                        queue.offer(choices[j][1]);
                    }else{
                        queue.offer(choices[j][0]);
                    }
                }
                //每次取得最高的分数
                int score = 0, winCnt = 0, cur = 0;
                while(!queue.isEmpty()){
                    score += queue.poll();
                    if(score >= targets[cur]) winCnt++;
                    cur++;
                }
                res = Math.max(res, winCnt);
            }
        }
        System.out.println(res);
    }
}